//
//  ProblemOffer56-2.swift
//  TestProject
//
//  Created by 武侠 on 2021/7/15.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 剑指 Offer 56 - II. 数组中数字出现的次数 II ✅
 在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
 示例 1：
     输入：nums = [3,4,3,3]
     输出：4
 示例 2：
     输入：nums = [9,1,7,9,7,9,7]
     输出：1
 限制：
     1 <= nums.length <= 10000
     1 <= nums[i] < 2^31
 */
@objcMembers class ProblemOffer56_2: NSObject {
    func solution() {
        print(singleNumber([3,4,3,3]))
        print(singleNumber([9,1,7,9,7,9,7]))
    }
    /*
     方法一：最简单的Map统计
     */
    func singleNumberMap(_ nums: [Int]) -> Int {
        var map:[Int: Int] = [:]
        for n in nums {
            map[n, default: 0] += 1
        }
        for key in map.keys {
            if map[key] == 1 {
                return key
            }
        }
        return 0
    }
    
    /*
     方法二：数学统计
     result = (3 * (a+b+c) - (3*a + 3*b + c)) / 2
     
     a + b + c 可以通过set来得到
     3*a + 3*b + c  就是数组的和
     */
    func singleNumber(_ nums: [Int]) -> Int {
        let set = Set(nums)
        let sumSet = set.reduce(0, +)
        let sumNum = nums.reduce(0, +)
        
        return (sumSet * 3 - sumNum) / 2
    }
    /*
     方法三：二进制
     统计所有数的二进制里面 每位1的个数，例如：
     3,4,3,3
     0 0 1 1
     0 0 1 1
     0 0 1 1
     0 1 1 0
     
     0 1 3 3
     因为其他数都是3个，所以 % 3 得到的就是 单独的数
             %3
     0 1 0 0
     */
    func singleNumberOne(_ nums: [Int]) -> Int {
        var list:[Int] = Array(repeating: 0, count: 32)
        for n in nums {
            var t = 1
            for i in 0..<32 {
                list[i] += (n & t == 0 ? 0 : 1)
                t <<= 1
            }
        }
        
        var result = 0
        for (i, n) in list.enumerated() {
            result |= (n % 3) << i
        }
        
        return result
    }
    
    /*
     方法四：求导
     因为有3个状态：00 -> 01 -> 10，所以需要2位来记录这3个状态:two 和 one 记录2个状态
     一: 首先判断one的状态变化：
     1> 如果two是0: 那么有2个可能性：00 和 01;
        1.1> 下一个数字的这一位是1： 00 -> 01    01 -> 10, 只看one这位的变化，0->1, 1->0
             总结就是取反了： one = ～one
        1.2> 下一个数字的这一位是0:  00 -> 00    01 -> 01, 就是没有变化：0->0, 1->1
             总结就是不变：one = one
        1.3> 把2个结合起来就是 异或：one = one ^ n
     2> 如果two是1: 只有1个可能性：10
        2.1> 下一个数字的这一位是1： 10 -> 00, 只看one这位的变化，0->0
             总结就是不变： one = one = 0
        2.2> 下一个数字的这一位是0:  10 -> 10, 就是没有变化：0->0
             总结就是不变：one = one = 0
        2.3> 把2个结合起来就是 异或：one = 0
     3> 把这2个结合起来：
        3.1> two = 0 => one = one^n
             two = 1 => one = 0
             就是说：two是0，变成one^n，two是1，one变成0
             => one = one^n & ~two
     二：判断two的状态变化：
     1> 如果one是0: 那么有2个可能性：00 和 10;
        1.1> 下一个数字的这一位是1： 00 -> 01  10 -> 00, 只看one这位的变化，0->0, 1->0
             总结变成0：two = two = 0
        1.2> 下一个数字的这一位是0:  00 -> 00  10 -> 10, 就是没有变化：0->0, 1->1
             总结就是不变： two = two
        1.3> 把2个结合起来就是：two = two & ～n
     2> 如果one是1: 只有1个可能性：01
        2.1> 下一个数字的这一位是1： 01 -> 10, 只看two这位的变化，0->1
             总结就是变成1： two = ~two = 1
        2.2> 下一个数字的这一位是0:  01 -> 01, 就是没有变化：0->0
             总结就是变成0：two = two = 0
        2.3> 把2个结合起来就是：two = two ^ n
     3> 把这2个结合起来：
        3.1> one = 0 => two = two&~n
             one = 1 => two = two^n
             就是说：one是0，变成two&~n，one是1，two变成two^n
             => ？？？推导不出来了 看K神题解
     */
    func singleNumberOneY(_ nums: [Int]) -> Int {
        
        return 0
    }
}
